// BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。
// BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多，至于为什么，我们后面介绍了框架就很容易看出来了。
// 本文就由浅入深写两道 BFS 的典型题目，分别是「二叉树的最小高度」和「打开密码锁的最少步数」，手把手教你怎么写 BFS 算法。

// 一、算法框架

// 说框架的话，我们先举例一下 BFS 出现的常见场景好吧，问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离，这个例子听起来很枯燥，但是 BFS 算法问题其实都是在干这个事儿，把枯燥的本质搞清楚了，再去欣赏各种问题的包装才能胸有成竹嘛。
// 这个广义的描述可以有各种变体，比如走迷宫，有的格子是围墙不能走，从起点到终点的最短距离是多少？如果这个迷宫带「传送门」可以瞬间传送呢？
// 再比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？
// 再比如说连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？
// 本质上就是一幅「图」，让你从一个起点，走到终点，问最短路径。这就是 BFS 的本质，框架搞清楚了直接默写就好。

// 记住下面这个框架就 OK 了：

// 队列 q 就不说了，BFS 的核心数据结构；cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited。

type NODE = {
  adj: NODE[] // 相邻的节点
}
// 计算从起点 start 到终点 target 的最近距离
const BFS = (start: NODE, target: NODE) => {
  const q: NODE[] = [] // 核心数据结构
  const visited = new Set<NODE>()  // 避免走回头路
  q.push(start) // 将起点加入队列
  visited.add(start)
  let step = 0
  while (q.length) { // q 不为空
    let sz = q.length
    /* 将当前队列中的所有节点向四周扩散 */
    for (let i = 0; i < sz; i++) {
      const cur = q.pop()
      /* 划重点：这里判断是否到达终点 */
      if (cur == target) {
        return step;
      }
      for (const x of cur.adj) {
        if (!visited.has(x)) {
          q.push(x);
          visited.add(x);
        }
      }
    }
    step++;
  }
}



